JuliaFold

codeskills, coding, doc, julia    
  1. Transducers.jl
    1. Introduction
    2. 概念
    3. 对比迭代器
  2. FLoops.jl
  3. Bangbang.jl

Transducers.jl

Introduction

Clojure中Transducer的julia实现, 高效的函数式编程，要理解Transducer, 需要先理解函数式编程的基本概念。

更详细地了解Transducer, 请参考 Rich Hickey在Strange Loop的演讲
函数式编程(Functional Programming)

  • 函数是一等公民;

  • 高阶函数、纯函数;

  • 代码简洁、可维护性强、容易测试和重构;

高阶函数 处理函数的函数(宏?), 常用的高阶函数: map, filter, reduce等。

  • 函数复用和组合;

  • 延时计算和闭包;

  • 数据转换和映射、筛选过滤、积累聚合;

先来一个直观的例子感受一下Transducers的优势:

julia

using BenchmarkTools
using Transducers

xs = randn(100_000_000)

# 进行如下操作: 对每个x取sin函数，然后求和

# method1: these three works similarly
@benchmark sum(sin.(xs))
@benchmark sum(map(sin, xs))
@benchmark reduce(+, map(sin,xs))

BenchmarkTools.Trial: 6 samples with 1 evaluation.
 Range (min … max):  887.046 ms … 978.415 ms  ┊ GC (min … max): 0.00% … 6.41%
 Time  (median):     903.369 ms               ┊ GC (median):    1.37%
 Time  (mean ± σ):   919.349 ms ±  38.214 ms  ┊ GC (mean ± σ):  2.62% ± 3.04%

  █ ██              █                         █               █
  █▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  887 ms           Histogram: frequency by time          978 ms <

 Memory estimate: 762.94 MiB, allocs estimate: 4.


# method2: use transducer foldl, significant MEM saving
@benchmark foldl(+, Map(sin), xs)


BenchmarkTools.Trial: 7 samples with 1 evaluation.
 Range (min … max):  785.240 ms … 799.354 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     792.432 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   792.801 ms ±   5.172 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

  █                █ █           █       █                   ██
  █▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁█▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁██ ▁
  785 ms           Histogram: frequency by time          799 ms <

 Memory estimate: 16 bytes, allocs estimate: 1.


# method3: use multi-thread version foldxt (4 threads in test)
# time saving ~ 4 times
Threads.nthreads() # 4
@benchmark foldxt(+, Map(sin), xs)


BenchmarkTools.Trial: 24 samples with 1 evaluation.
 Range (min … max):  208.649 ms … 232.593 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     216.597 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   216.964 ms ±   5.479 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

        ▃          ▃          ▃█
  ▇▁▇▇▁▁█▁▇▁▁▇▁▁▇▁▇█▁▇▇▁▁▁▇▁▁▇██▁▁▁▇▇▁▁▇▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▇ ▁
  209 ms           Histogram: frequency by time          233 ms <

 Memory estimate: 1.98 KiB, allocs estimate: 22.

julia

可见, 合理应用Transducer进行函数式编程，可以有效减少内存占用、GC时间等, 提高效率。

概念

plain

foldl(step, xf, input, init=...)
   |   |    |     |
   |   |    |     `-- reducible
   |   |    |
   |   |    `-- transducer
   |   |
   |   `-- "bottom" (inner most) reducing function
   |
   `-- transducible process

plain

  • reducible: 可以适用reduce操作的数据;

  • transducer: reduce之前对数据进行处理的函数[集合], 称为变换函数xf, 可以分为两种:

    • iterator transformation: 使用xf(itr)方式的语法进行迭代器转换;

    • reducing function transformation: 使用xf'(rf)方式的语法进行reducing转换;

  • bottom: reducing函数, 有时也叫step或op;

  • transducible process: 组配整个过程的高阶函数;

  • eduction: Transducer中的reducible对象, 适配foldl等函数从而提升效率;

Clojure中狭义的Transducer Rich Hickey最初提出的Transducer是对reducing步骤的变换, 因此, 在Clojure(和很多其他语言中), \(xf\) 指代本库中的xf'。

  • xf'可以用函数组合函数∘来进行整合:

julia

# 以下形式等价
rf = xf1'(xf2'(...(xfn'(rf0))))
rf = (xf1' ∘ xf2' ∘ ... ∘ xfn')(rf0)
rf = (xfn ∘ ... ∘ xf2 ∘ xf1)'(rf0) # 注意,'反向
rf = (xf1 ⨟ xf2 ⨟ ... ⨟ xfn)(rf0)

julia

  • Inner transducer: 给定rf = xf1' ∘ xf2', xf2是rf的内部transducer。

  • Executor: 执行器, 指定transducer的执行机制, 如SequentialEx, ThreadedEx, DistributedEx等, 通常不需要手动配置。

对比迭代器

还是用一个例子来证明:

julia

using Transducers
xf = opcompose(Filter(iseven), Map(x -> 2x))

collect(xf, 1:6) # 4, 8, 12
foldl(+, xf, 1:6) # 24

# same operation in iterator:
f(x) = 2x
imap = Base.Iterators.Generator
mapfoldl(f, +, filter(iseven, input), init=0)
foldl(+, imap(f, filter(iseven, input)))

julia

二者最大的区别, 是transducer的xf组合发生在计算阶段, 而iterator的组合发生在输入阶段, 把二者的代码分别转换成更低级代码为:

julia

# iterator code can be lowered to:
function map_filter_iterators(xs, init)
    ret = iterate(xs)
    ret === nothing && return init
    acc = init
    @goto filter
    local state, x
    while true
        while true                                    # input
            ret = iterate(xs, state)                  #
            ret === nothing && return acc             #
            @label filter                             #
            x, state = ret                            #
            iseven(x) && break             # filter   :
        end                                #          :
        y = 2x              # imap         :          :
        acc += y    # +     :              :          :
    end             # :     :              :          :
    #                 + <-- imap <-------- filter <-- input
end

# On the other hand, the code using transducers is lowered to:
function map_filter_transducers(xs, init)
    acc = init
    #              input -> Filter --> Map --> +
    for x in xs  # input    :          :       :
        if iseven(x)  #     Filter     :       :
            y = 2x    #                Map     :
            acc += y  #                        +
        end
    end
    return acc
end

xs = [6, 8, 1, 4, 5, 6, 6, 7, 9, 9, 7, 8, 6, 8, 2, 5, 2, 4, 3, 7]
@assert map_filter_iterators(xs, 0) == map_filter_transducers(xs, 0)

julia

FLoops.jl

Bangbang.jl